Đếm số nguyên

Đây là ví dụ đơn giản trong áp dụng nguyên lý bao hàm-loại trừ, xét câu hỏi sau:[7]

Có bao nhiêu số nguyên trong tập {1, …, 100} không chia hết cho 2, 3 hoặc 5?

Gọi S = {1,…,100} và P1 là tính chất số nguyên chia hết cho 2, P2 là tính chất số nguyên chia hết cho 3 và P3 là tính chất số nguyên chia hết cho 5. Gọi Ai là tập con của S chứa các phần tử có tính chất Pi, ta đếm được rằng: |A1| = 50, |A2| = 33, và |A3| = 20. Có 16 số nguyên chia hết cho 6, 10 số chia hết cho 10, và 6 số chia hết cho 15. Và cuối cùng, chỉ có 3 số chia hết cho 30, nên số các số nguyên không chia hết cho bất kỳ 2, 3 hoặc 5 được tính bằng:

100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.

Đếm số mất thứ tự

Một câu hỏi phức tạp hơn trên được phát biểu như sau.

Giả sử có bộ n lá bài được đánh số từ 1 đến n. Ta gọi lá số m nằm đúng vị trí nếu nó là lá thứ m trong bộ bài. Hỏi có bao nhiêu cách, (ký hiệu là W), để xáo bộ bài sao cho trong bộ có ít nhất 1 lá nằm đúng vị trí?

Ta bắt đầu bằng cách định nghĩa Am, là số các thứ tự bài mà trong đó lá thứ m nằm đúng vị trí. Khi đó, số các thứ tự W, với ít nhất một lá nằm đúng vị trí được tính bởi

W = | ⋃ m = 1 n A m | . {\displaystyle W=\left|\bigcup _{m=1}^{n}A_{m}\right|.}

Áp dụng nguyên lý bao hàm-loại trừ,

W = ∑ m 1 = 1 n | A m 1 | − ∑ 1 ⩽ m 1 < m 2 ⩽ n | A m 1 ∩ A m 2 | + ⋯ + ( − 1 ) p − 1 ∑ 1 ⩽ m 1 < ⋯ < m p ⩽ n | A m 1 ∩ ⋯ ∩ A m p | + ⋯ {\displaystyle W=\sum _{m_{1}=1}^{n}|A_{m_{1}}|-\sum _{1\leqslant m_{1}<m_{2}\leqslant n}|A_{m_{1}}\cap A_{m_{2}}|+\cdots +(-1)^{p-1}\sum _{1\leqslant m_{1}<\cdots <m_{p}\leqslant n}|A_{m_{1}}\cap \cdots \cap A_{m_{p}}|+\cdots }

Mỗi giá trị A m 1 ∩ ⋯ ∩ A m p {\displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}}} biểu diễn tập các phép xáo trong đó có ít nhất p giá trị m1, …, mp đang nằm đúng vị trí. Lưu ý rằng số các xáo trộn với ít nhất p giá trị nằm đúng chỉ phụ thuộc vào p, chứ không trên giá trị cụ thể của m {\displaystyle m} . Ví dụ chẳn hạn, số các phép xáo có vị trí thứ 1, thứ ba và thứ 17 nằm đúng bằng với số các phép xáo có vị trí thứ 2, thứ 5 và thứ 14 nằm đúng. Ta chỉ quan tâm rằn trong n lá đó và trong trường hợp xét ba lá, có 3 vị trí được chọn là vị trí đúng. Do đó có ( n p ) {\textstyle {n \choose p}} phần tử bằng nhau trong tổng thứ pth (xem tổ hợp).

W = ( n 1 ) | A 1 | − ( n 2 ) | A 1 ∩ A 2 | + ⋯ + ( − 1 ) p − 1 ( n p ) | A 1 ∩ ⋯ ∩ A p | + ⋯ {\displaystyle W={n \choose 1}|A_{1}|-{n \choose 2}|A_{1}\cap A_{2}|+\cdots +(-1)^{p-1}{n \choose p}|A_{1}\cap \cdots \cap A_{p}|+\cdots }

| A 1 ∩ ⋯ ∩ A p | {\displaystyle |A_{1}\cap \cdots \cap A_{p}|} là số các thứ tự có p phần tử nằm đúng vị trí, và bằng với số xếp thứ tự với n − p phần tử còn lại, hay (n − p)!.Do đó cuối cùng ta được:

W = ( n 1 ) ( n − 1 ) ! − ( n 2 ) ( n − 2 ) ! + ⋯ + ( − 1 ) p − 1 ( n p ) ( n − p ) ! + ⋯ = ∑ p = 1 n ( − 1 ) p − 1 ( n p ) ( n − p ) ! = ∑ p = 1 n ( − 1 ) p − 1 n ! p ! ( n − p ) ! ( n − p ) ! = ∑ p = 1 n ( − 1 ) p − 1 n ! p ! {\displaystyle {\begin{aligned}W&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+\cdots +(-1)^{p-1}{n \choose p}(n-p)!+\cdots \\&=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!(n-p)!}}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!}}\end{aligned}}}

Hoán vị mà không có lá nào nằm đúng vị trí được gọi là mất thứ tự. Lấy n! là số các hoán vị, xác suất Q rằng một phép xáo ngẫu nhiên sẽ sinh ra xáo trộn được tính bởi

Q = 1 − W n ! = ∑ p = 0 n ( − 1 ) p p ! , {\displaystyle Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},}

đây là dạng rút gọn về n + 1 phần tử của khai triển Taylor của e−1. Do đó xác suất đoán một thứ tự cho một bộ bài đã được xáo và sai mọi lá rơi vào khoảng e−1 hay 37%.